package com.yjz.leetcode.二叉树学习.二三四树;

/**
 * @author :yuanJinZhong
 * @description: 234树 数据结构类
 * @date :2018/12/2-10:34
 */
public class Tree234 {
  private Node root = new Node();

  /**
   * 从234树中查找数据
   *
   * @param key
   * @return
   */
  public int find(Comparable key) {
    Node current = root;
    //子节点下标
    int childIndex;

    while (true) {
      if ((childIndex = current.findItem(key)) != -1) {
        return childIndex;
      } else if (current.isLeaf()) {
        return -1;
      } else {
        current = getNextChild(current, key);
      }
    }
  }

  /**
   * 查找指定节点的下一个节点
   *
   * @param theNode
   * @param theValue
   * @return
   */
  public Node getNextChild(Node theNode, Comparable theValue) {
    int j;
    int numItems = theNode.getNumItems();
    for (j = 0; j < numItems; j++) {
      if (theValue.compareTo(theNode.getItem(j).getData()) < 0) {
        return theNode.getChild(j);
      }
    }
    return theNode.getChild(j);
  }

  /**
   * 插入数据项
   */
  public void insert(Comparable data) {
    Node current = root;
    DataItem dataItem = new DataItem(data);
    while (true) {
      //如果节点数据项满了,则分裂节点
      if (current.isDataItemFull()) {
        split(current);
        current = current.getParent();
        current = getNextChild(current, dataItem.getData());
      } else if (current.isLeaf()) {
        break;//跳出while(true)
      } else {
        current = getNextChild(current, dataItem.getData());
      }
    }//end while(true)
    current.insertItem(dataItem);
  }

  /**
   * 分列节点
   *
   * @param thisNode
   */
  public void split(Node thisNode) {

    /**
     * itemB 和itemC 不是随便起的
     *
     * 而是根据节点分列的原则起的:
     * 　1、节点分裂
     　　一、创建一个新的空节点，它是要分裂节点的兄弟，在要分裂节点的右边；

     　　二、数据项C移到新节点中；

     　　三、数据项B移到要分裂节点的父节点中；

     　　四、数据项A保留在原来的位置；

     　　五、最右边的两个子节点从要分裂处断开，连到新节点上。

     *   2、根的分裂
     　　如果一开始查找插入节点时就碰到满的根节点，那么插入过程更复杂：

     　　①、创建新的根节点，它是要分裂节点的父节点。

     　　②、创建第二个新的节点，它是要分裂节点的兄弟节点；

     　　③、数据项C移到新的兄弟节点中；

     　　④、数据项B移到新的根节点中；

     　　⑤、数据项A保留在原来的位置；

     　　⑥、要分裂节点最右边的两个子节点断开连接，连到新的兄弟节点中。
     */
    DataItem itemB, itemC;
    Node parent, child2, child3;
    int itemIndex;
    itemC = thisNode.removeItem();
    itemB = thisNode.removeItem();
    child2 = thisNode.disConnectChild(2);
    child3 = thisNode.disConnectChild(3);
    //新的右边节点
    Node newRight = new Node();
    //如果当前节点是根节点则执行根分裂
    if (thisNode == root) {
      root = new Node();
      parent = root;
      root.connectChild(0, thisNode);
    } else {
      parent = thisNode.getParent();
    }
    //处理父节点
    //原来的数据项B提到父节点
    itemIndex = parent.insertItem(itemB);
    //查看父节点有多少数据项
    int n = parent.getNumItems();
    for (int j = n - 1; j > itemIndex; j--) {
      Node temp = parent.disConnectChild(j);
      parent.connectChild(j + 1, temp);
    }
    parent.connectChild(itemIndex + 1, newRight);
    //处理新建的右节点
    newRight.insertItem(itemC);
    newRight.connectChild(0, child2);
    newRight.connectChild(1, child3);
  }

  //从根节点开始打印所有节点数据
  public void displayTree() {
    recDisplayTree(root, 0, 0);
  }

  //打印指定树节点及子节点数据
  private void recDisplayTree(Node thisNode, int level, int childNumber) {
    System.out.println("levle=" + level + " child=" + childNumber + " ");
    thisNode.disPlayNodeData();
    int numItems = thisNode.getNumItems();
    for (int j = 0; j < numItems + 1; j++) {
      Node nextNode = thisNode.getChild(j);
      if (nextNode != null) {
        recDisplayTree(nextNode, level + 1, j);
      } else {
        return;
      }
    }
  }
}
